package string

// 最长无重复子串
// lengthOfLongestSubstring
// e.g. "abcabcbb" => 3
func lengthOfLongestSubstring(s string) int {
	charIndexMap := make(map[byte]int)
	maxLength := 0
	left := 0
	for right := 0; right < len(s); right++ {
		if index, ok := charIndexMap[s[right]]; ok && index >= left {
			left = index + 1
		}
		charIndexMap[s[right]] = right
		if maxLength < right-left+1 {
			maxLength = right - left + 1
		}
	}
	return maxLength
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func reverse(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

// reverse 2k characters in a string
// e.g. "abcde", k=2 => "bacde"
// e.g. "abcdef", k=2 => "bacdfe"
// e.g. "abcdefg", k=3 => "cbadefg"
// e.g. "abcdefg", k=4 => "dcbaefg"
func reverseK(s string, k int) string {
	r := []rune(s)
	for i := 0; i < len(r); i += 2 * k {
		j := i + k - 1
		// i = 4; j = 5; len(r) = 5
		if j >= len(r) {
			j = len(r) - 1
		}
		for x, y := i, j; x < y; x, y = x+1, y-1 {
			r[x], r[y] = r[y], r[x]
		}
	}
	return string(r)
}

func getNext(s string) []int {
	next := make([]int, len(s))
	next[0] = -1
	i, j := 0, -1
	for i < len(s)-1 {
		if j == -1 || s[i] == s[j] {
			i++
			j++
			next[i] = j
		} else {
			j = next[j]
		}
	}
	return next
}
